// https://www.lintcode.com/problem/subdomain-visit-count/

public class Solution {
    /**
     * @param cpdomains: a list cpdomains of count-paired domains
     * @return: a list of count-paired domains
     */
    public List<String> subdomainVisits(String[] cpdomains) {
        // Write your code here
        List<String> ret = new ArrayList<>();
        HashMap<String, Integer> map = new HashMap<>();
        for (String cpdomain : cpdomains) {
            String[] parts = cpdomain.split(" ");
            int count = Integer.parseInt(parts[0]);
            String[] domains = parts[1].split("\\."); // 不能直接用.
            for (int i = 0; i < domains.length; ++i) {
                StringBuilder sb = new StringBuilder();
                sb.append(domains[i]);
                for (int j = i + 1; j < domains.length; ++j) {
                    sb.append(".");
                    sb.append(domains[j]);
                }
                String sub = sb.toString();
                if (!map.containsKey(sub)) {
                    map.put(sub, count);
                } else {
                    map.put(sub, map.get(sub) + count);
                }
            }
        }
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            ret.add(String.valueOf(entry.getValue()) + " " + entry.getKey());
        }
        return ret;
    }
}